# @Time : 2020/6/24 17:22
# @Author : Fioman 
# @Phone : 13149920693
import bisect
import sys

fruits = ['grape', 'raspberry', 'apple', 'banana']
fruits_sorted = sorted(fruits)
print("fruits_sorted = {}".format(fruits_sorted))
print("fruits = {}".format(fruits))
fruits.sort()
print("fruits = {}".format(fruits))

# 使用bisect来管理已经排序的序列
"""
bisect模块包含两个主要的函数,bisect和insort,两个函数都利用二分查找算法来在有序序列中查找或插入元素.
1> 使用bisect来搜索
bisect(haystack,needle) 在haystack里搜索needle(针)的位置,该位置满足的条件是,把needle插入到这个位置之后,haystack还能保持升序.也就是在说这个函数返回的位置
前面的值,都小于或等于needle的值.你可以先使用bisect(haystack,needle)查找位置index,再用haystack.insert(index,needle)来插入新值.但是你也可以用insort来一步到位.
并且后者的速度更快一些.
"""
HAYSTACK = [1, 4, 5, 6, 8, 12, 15, 20, 21, 23, 23, 26, 29, 30]
NEEDLES = [0, 1, 2, 5, 8, 10, 22, 23, 29, 30, 31]
ROW_FMT = '{0:2d} @ {1:2d} {2}{0:<2d}'


def demo(bisect_fn):
    for needle in reversed(NEEDLES):
        position = bisect_fn(HAYSTACK, needle)
        offset = position * "  |"
        print(ROW_FMT.format(needle, position, offset))


if __name__ == '__main__':
    if sys.argv[-1] == "left":
        bisect_fn = bisect.bisect_left
    else:
        bisect_fn = bisect.bisect_right

    print("DEMO:", bisect_fn.__name__)
    print("haystack ->", ' '.join("{}".format(n for n in HAYSTACK)))
    demo(bisect_fn)

    # 使用bisect.insort 插入新的元素,并且排序,不但具有插入新元素的功能,而且还自带排序.
    # insort(seq,item) 把变量item插入到序列seq中,并且能保持seq的升序顺序.

    import random

    SIZE = 7
    random.seed(1729)
    my_list = []
    for i in range(SIZE):
        new_item = random.randrange(SIZE * 2)
        bisect.insort(my_list, new_item)
        print("%2d -> " % new_item, my_list)
